Field of the Disclosure
This application relates to sorting and in particular to sorting using multiple processing modules.
Description of the Related Art
The widely accepted value for the minimum number of comparison operations to sort a large list of N items is N log 2(N). Sorting a very large list of one billion items, for example, still requires roughly 30B comparisons. Each of these comparisons can also require many clock cycles of the computing system. 30B comparisons might actually take 300B clocked operations. In Big Data analytics, weather prediction, nuclear calculations, astrophysics, genetics, public health, and many other disciplines, there is a frequent need to sort very large datasets. That implies computational resources than can literally fill buildings with racks of servers to service these sorting needs. To the extent one can improve on this N log 2(N) limitation, or otherwise improve sorting operations, one can improve on the capital infrastructure and associated operational costs for computing systems.